package com.kitty.record.kittyalgorithm.audition;

import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;

/**
 * 给定一棵二叉树，设计一个算法，
 * 创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。
 * 返回一个包含所有深度的链表的数组。
 *
 * 示例：
 * 输入：[1,2,3,4,5,null,7,8]
 *         1
 *        /  \
 *       2    3
 *      / \    \
 *     4   5    7
 *    /
 *   8
 * 输出：[[1],[2,3],[4,5,7],[8]]
 * 树 广度优先搜索
 * //todo 需要进一步了解二叉树的广度优先搜索算法
 * @Author SHEN
 * @Date 2020/12/18
 */
public class LeetCode0403 {

    public static void main(String[] args) {

    }

    public ListNode[] listOfDepth(TreeNode tree) {
        if(tree != null){
            int deep = getDeep(tree);
            ListNode[] res = new ListNode[deep];

            dfs(tree,0,res);
            return res;

        }
        return new ListNode[0];
    }

    //通过递归获取二叉树的深度
    public static int getDeep(TreeNode treeNode){
        if(treeNode == null){
            return 0;
        }
        return Math.max(getDeep(treeNode.left),getDeep(treeNode.right))+1;
    }
    //二叉树的深度优先搜索
    public static void dfs(TreeNode treeNode,int deep,ListNode[] res){

        if(treeNode != null){

            ListNode listNode = new ListNode(treeNode.val);
            if(res[deep] == null){
                res[deep] = listNode;
            }else{
                listNode.next = res[deep];
                res[deep] = listNode;
            }
            dfs(treeNode.left,deep+1,res);
            dfs(treeNode.right,deep+1,res);
        }

    }





    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}




